{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Triangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTotal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三角形最小路径和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个三角形 <code>triangle</code> ，找出自顶向下的最小路径和。</p>\n",
    "\n",
    "<p>每一步只能移动到下一行中相邻的结点上。<strong>相邻的结点 </strong>在这里指的是 <strong>下标</strong> 与 <strong>上一层结点下标</strong> 相同或者等于 <strong>上一层结点下标 + 1</strong> 的两个结点。也就是说，如果正位于当前行的下标 <code>i</code> ，那么下一步可以移动到下一行的下标 <code>i</code> 或 <code>i + 1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>如下面简图所示：\n",
    "   <strong>2</strong>\n",
    "  <strong>3</strong> 4\n",
    " 6 <strong>5</strong> 7\n",
    "4 <strong>1</strong> 8 3\n",
    "自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>triangle = [[-10]]\n",
    "<strong>输出：</strong>-10\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= triangle.length <= 200</code></li>\n",
    "\t<li><code>triangle[0].length == 1</code></li>\n",
    "\t<li><code>triangle[i].length == triangle[i - 1].length + 1</code></li>\n",
    "\t<li><code>-10<sup>4</sup> <= triangle[i][j] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以只使用 <code>O(n)</code> 的额外空间（<code>n</code> 为三角形的总行数）来解决这个问题吗？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [triangle](https://leetcode.cn/problems/triangle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [triangle](https://leetcode.cn/problems/triangle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2],[3,4],[6,5,7],[4,1,8,3]]', '[[-10]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        if not triangle:\n",
    "            return 0\n",
    "        \n",
    "        if len(triangle) == 1:\n",
    "            return triangle[0][0]\n",
    "        \n",
    "        rows = len(triangle)\n",
    "        cols = len(triangle[rows-1])\n",
    "        \n",
    "        dp = [[0 for _ in range(len(triangle[i]))] for i in range(rows)]\n",
    "        dp[rows-1] = triangle[rows-1]\n",
    "        \n",
    "        for i in range(rows-2, -1, -1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]\n",
    "                \n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "        \"\"\"\n",
    "        :type triangle: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        memo = triangle[-1]\n",
    "        n = len(memo)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(i + 1):\n",
    "                memo[j] = triangle[i][j] + min(memo[j], memo[j + 1])\n",
    "        return memo[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "        \"\"\"\n",
    "        :type triangle: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        rows = len(triangle)\n",
    "        res = [sys.maxsize for _ in range(rows)]\n",
    "        temp = [sys.maxsize for _ in range(rows)]\n",
    "        res[0] = triangle[0][0]\n",
    "        for i in range(1, rows):\n",
    "            col = len(triangle[i])\n",
    "            for j in range(col):\n",
    "                one, two = res[j-1], res[j]\n",
    "                temp[j] = triangle[i][j]+min(one, two)\n",
    "            res = copy.deepcopy(temp)\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "        \"\"\"\n",
    "        :type triangle: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        for i in range(1, len(triangle)):\n",
    "            triangle[i][0] += triangle[i-1][0]\n",
    "            for j in range(1, len(triangle[i]) - 1):\n",
    "                triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])\n",
    "            triangle[i][-1] += triangle[i-1][-1]\n",
    "        return min(triangle[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "        \"\"\"\n",
    "        :type triangle: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 初始值\n",
    "        dp = triangle\n",
    "        for row in range(len(triangle) - 2, -1, -1):\n",
    "            row_len = len(triangle[row])\n",
    "            for j in range(row_len):\n",
    "                dp[row][j] = min(dp[row + 1][j], dp[row + 1][j + 1]) + dp[row][j]\n",
    "\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "        \"\"\"\n",
    "        :type triangle: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        for i in range(1,len(triangle)):\n",
    "            for j in range(len(triangle[i])):\n",
    "                if j == 0: \n",
    "                    triangle[i][j] = triangle[i-1][j] + triangle[i][j]\n",
    "                elif j == (len(triangle[i])-1): \n",
    "                    triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]\n",
    "                else:\n",
    "                    triangle[i][j] = min(triangle[i-1][j-1] + triangle[i][j], triangle[i-1][j] + triangle[i][j])\n",
    "        print(triangle)\n",
    "        return min(triangle[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        for i in range(len(triangle)-2,-1,-1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                triangle[i][j] += min(triangle[i+1][j],triangle[i+1][j+1])\n",
    "        return triangle[0][0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "        \"\"\"\n",
    "        :type triangle: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not triangle or not triangle[0]:\n",
    "            return 0\n",
    "        dp=[[0 for i in range(len(triangle[j]))] for j in range(len(triangle))]\n",
    "        for i in range(len(dp[-1])):\n",
    "            dp[-1][i]=triangle[-1][i]\n",
    "        for i in range(len(dp)-2,-1,-1):\n",
    "            for j in range(len(dp[i])):\n",
    "                dp[i][j]=triangle[i][j]+min(dp[i+1][j],dp[i+1][j+1])\n",
    "        print(dp)\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: 'List[List[int]]') -> 'int':\n",
    "        n=len(triangle)    #n为三角形的总行数\n",
    "        dp=[[0 for x in range(n)] for x in range(n)]\n",
    "        if(n==0):\n",
    "            return 0\n",
    "        elif(n==1):\n",
    "            dp[0][0]=triangle[0][0]\n",
    "        else:\n",
    "            dp[0][0]=triangle[0][0]\n",
    "            for i in range(1,n):\n",
    "                dp[i][0]=dp[i-1][0]+triangle[i][0]\n",
    "                if(i>1):\n",
    "                    for j in range(1,i):\n",
    "                        dp[i][j]=min(dp[i-1][j-1]+triangle[i][j],triangle[i][j]+dp[i-1][j])\n",
    "                dp[i][i]=dp[i-1][i-1]+triangle[i][i]\n",
    "        print(dp)\n",
    "        return min(dp[n-1])\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "        \"\"\"\n",
    "        :type triangle: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        w = len(triangle[-1])\n",
    "        dp= [[float('inf') for _ in range(w)] for _ in range(w) ]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(1, w):\n",
    "            for j in range(len(triangle[i])):\n",
    "                cur = dp[i-1][j] if j == 0 else min(dp[i-1][j], dp[i-1][j-1])\n",
    "                dp[i][j] = triangle[i][j]+cur\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "        \"\"\"\n",
    "        :type triangle: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(triangle) == 0:\n",
    "            return 0\n",
    "        dp = copy.deepcopy(triangle)\n",
    "        for i in range(len(triangle)-1):\n",
    "            for j in range(len(dp[i])):\n",
    "                dp[i][j] = 0\n",
    "        print(dp,triangle)\n",
    "        for i in range(len(triangle)-2,-1,-1):\n",
    "            for j in range(len(dp[i])):\n",
    "                print(min(dp[i+1][j],dp[i+1][j+1]),triangle[i][j])\n",
    "                dp[i][j] = min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = 1000000\n",
    "        self.m = {}\n",
    "    def minimumTotal(self, triangle):\n",
    "        \"\"\"\n",
    "        :type triangle: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 利用一个哈希表存每个点后和的最小值\n",
    "        def dfs(l,p,r):\n",
    "            if l == L:\n",
    "                if r < self.s:\n",
    "                    self.s = r\n",
    "                return r\n",
    "            if (l,p) in self.m:\n",
    "                return self.m[(l,p)] + r\n",
    "            else:\n",
    "                r1 = dfs(l+1,p,r+triangle[l][p])\n",
    "                r2 = dfs(l+1,p+1,r+triangle[l][p])\n",
    "                self.m[(l,p)] = min(r1-r,r2-r)\n",
    "                if r1 < self.s:\n",
    "                    self.s = r1\n",
    "                if r2 < self.s:\n",
    "                    self.s = r2\n",
    "                return min(r1-r,r2-r) + r\n",
    "            return\n",
    "        if not triangle:\n",
    "            return 0\n",
    "        L = len(triangle)\n",
    "        dfs(0,0,0)\n",
    "        return self.s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        row = len(triangle)\n",
    "        dp = [0] * row\n",
    "        for i in range(len(triangle[-1])):\n",
    "            dp[i] = triangle[-1][i]\n",
    "        #print(dp)\n",
    "        for i in range(row - 2, -1, -1):\n",
    "            for j in range(i + 1):\n",
    "                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]\n",
    "        return dp[0]   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "        ##动态规划都是buttom-up to down 的写法\n",
    "        ##要求空间复杂度为O(n)\n",
    "        ## dp[i][j] = triangle[i][j] + min(dp[i-1][j],dp[i-1][j-1])\n",
    "        h = len(triangle)\n",
    "        if h==0:\n",
    "            return 0\n",
    "        dp = [0 for c in range(1,h+1)]\n",
    "        dp[0]= triangle[0][0]\n",
    "        import sys\n",
    "        for i in range(1,h):\n",
    "            for j in range(i,-1,-1):\n",
    "                curval = sys.maxsize\n",
    "                if i-1>=j:\n",
    "                    curval = min(curval,dp[j])\n",
    "                if j-1>=0:\n",
    "                    curval = min(curval,dp[j-1])\n",
    "                dp[j]= triangle[i][j]+curval\n",
    "                    \n",
    "\n",
    "        import sys\n",
    "        sumtotal = sys.maxsize\n",
    "        for i in range(h):\n",
    "            sumtotal = min(sumtotal,dp[i])\n",
    "        return sumtotal        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        mini ,m = triangle[-1],len(triangle)\n",
    "        for i in range(m-2,-1,-1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                mini[j] = triangle[i][j]+min(mini[j],mini[j+1])\n",
    "        return mini[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, tr: List[List[int]]) -> int:\n",
    "        if not tr or not tr[0]: return 0\n",
    "        l = len(tr)\n",
    "        dp = tr[-1].copy()\n",
    "        for row in tr[-2::-1]:\n",
    "            for j in range(len(row)):\n",
    "                dp[j] = min(dp[j], dp[j+1]) + row[j]\n",
    "        return dp[0]\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumTotal(self, tr: List[List[int]]) -> int:\n",
    "#         if not tr: return 0\n",
    "#         if len(tr) == 1: return tr[0][0]\n",
    "#         dp = tr[-1].copy()\n",
    "#         for i, it in enumerate(tr[::-1]):\n",
    "#             if i == 0: continue\n",
    "#             for j in range(len(it)):\n",
    "#                 dp[j] = it[j] + min(dp[j], dp[j+1])\n",
    "#         return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle):\n",
    "        n=len(triangle)\n",
    "        dp=triangle[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(i+1):\n",
    "                dp[j]=min((dp[j]+triangle[i][j]),dp[j+1]+triangle[i][j])\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "    # def minimumTotal(self, triangle) -> int:\n",
    "        for r in range(len(triangle) - 2, -1, -1):\n",
    "            for c in range(len(triangle[r])):\n",
    "                triangle[r][c] += min(triangle[r+1][c:c+2])\n",
    "                \n",
    "        return triangle[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        if not triangle:\n",
    "            return 0\n",
    "        for i in range(1, len(triangle)):\n",
    "            for j in range(len(triangle[i])):\n",
    "                if j == 0:\n",
    "                    triangle[i][j] = triangle[i][j] + triangle[i-1][j]\n",
    "                elif j == len(triangle[i]) - 1:\n",
    "                    triangle[i][j] = triangle[i][j] + triangle[i-1][j-1]\n",
    "                else:\n",
    "                    triangle[i][j] = triangle[i][j] + min(triangle[i-1][j], triangle[i-1][j-1])\n",
    "        return min(triangle[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [[0] * (len(i)) for i in triangle]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(1, len(triangle)):\n",
    "            dp[i][0] = dp[i - 1][0] + triangle[i][0]\n",
    "            for j in range(1, i):\n",
    "                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]\n",
    "            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]\n",
    "        \n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        size=len(triangle)\n",
    "        dp=[[0 for i in range(size)] for x in range(size)]\n",
    "\n",
    "        dp[size-1]=triangle[-1]\n",
    "\n",
    "        for i in range(size-2,-1,-1):\n",
    "            for j in range(len(triangle[i])):\n",
    "                if j<=i:\n",
    "                    dp[i][j]=triangle[i][j]+min(dp[i+1][j],dp[i+1][j+1])\n",
    "        return dp[0][0]\n",
    "                    \n",
    "\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        sum_triange = []\n",
    "        tmp = []\n",
    "        tri_len = len(triangle)\n",
    "        for i in range(0, tri_len):\n",
    "            self.bianli(i, sum_triange, tmp, triangle)\n",
    "            sum_triange.append(list(tmp))\n",
    "            tmp = []\n",
    "        print(sum_triange)\n",
    "        return min(sum_triange[tri_len - 1])\n",
    "\n",
    "    def bianli(self, i, sum_triange, tmp, triangle):\n",
    "        for j in range(0, i + 1):\n",
    "            if i == 0 and j == 0:\n",
    "                tmp.append(triangle[i][j])\n",
    "            elif j == 0:\n",
    "                tmp.append(sum_triange[i - 1][j] + triangle[i][j])\n",
    "            elif j == i:\n",
    "                tmp.append(sum_triange[i - 1][j - 1] + triangle[i][j])\n",
    "            else:\n",
    "                tmp.append(min(sum_triange[i - 1][j - 1], sum_triange[i - 1][j]) + triangle[i][j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        k = len(triangle)\n",
    "        if k == 1:\n",
    "            return triangle[0][0]\n",
    "        dp = [0]*k\n",
    "        dp[0] = triangle[0][0]\n",
    "        for i in range(1,k):\n",
    "            dp[i] = dp[i-1]+triangle[i][i]\n",
    "            for j in range(i - 1, 0, -1):\n",
    "                dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j]\n",
    "            dp[0] += triangle[i][0]\n",
    "                \n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        if len(triangle) == 1:\n",
    "            return triangle[0][0]\n",
    "        dp1 = [10 ** 5] * len(triangle)\n",
    "        dp0 = [10 ** 5] * len(triangle)\n",
    "        dp0[0] = dp1[0] = triangle[0][0]\n",
    "        for i in range(1, len(triangle)):\n",
    "            for j in range(len(triangle[i])):\n",
    "                if j > 0:\n",
    "                    dp1[j] = min(dp0[j], dp0[j - 1])\n",
    "                dp1[j] += triangle[i][j]\n",
    "            dp0 = dp1[:]\n",
    "        return min(dp1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        temp = [0] * n\n",
    "        temp[0] = triangle[0][0]\n",
    "        ans = triangle[0][0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(i, -1, -1):\n",
    "                if j == i:\n",
    "                    temp[j] = temp[j - 1] + triangle[i][j]\n",
    "                    ans = temp[j]\n",
    "                elif j == 0:\n",
    "                    temp[0] += triangle[i][0]\n",
    "                else:\n",
    "                    temp[j] = min(temp[j - 1], temp[j]) + triangle[i][j]\n",
    "                ans = min(ans, temp[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n=len(triangle)\n",
    "        temp=[0 for _ in range(n)]\n",
    "        temp[0]=triangle[0][0]\n",
    "        level=1\n",
    "        while level<n:\n",
    "            temp[level]=temp[level-1]+triangle[level][level]\n",
    "            for i in range(level-1,0,-1):\n",
    "                if temp[i]<temp[i-1]:\n",
    "                    temp[i]+=triangle[level][i]\n",
    "                else:\n",
    "                    temp[i]=temp[i-1]+triangle[level][i]\n",
    "            temp[0]+=triangle[level][0]\n",
    "            level+=1\n",
    "        return min(temp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        depth = len(triangle)\n",
    "        dp = triangle\n",
    "\n",
    "        for i in range(1, depth):\n",
    "            dp[i][0] = dp[i][0] + dp[i-1][0]\n",
    "            dp[i][i] = dp[i][i] + dp[i-1][i-1]\n",
    "        \n",
    "        if depth <= 2:\n",
    "            return min(dp[depth-1])\n",
    "\n",
    "        for i in range(2, depth):\n",
    "            for j in range(1, i):\n",
    "                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + dp[i][j]\n",
    "        \n",
    "\n",
    "        return min(dp[depth-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        m=len(triangle)\n",
    "        for i in range(1,m):\n",
    "            triangle[i][0]+=triangle[i-1][0]\n",
    "            triangle[i][-1]+=triangle[i-1][-1]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1, len(triangle[i])-1):\n",
    "                triangle[i][j]+=min(triangle[i-1][j-1], triangle[i-1][j])\n",
    "        return min(triangle[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        if n <= 1:\n",
    "            return triangle[0][0]\n",
    "        dp = copy.deepcopy(triangle)\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            for j in range(i + 1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j]\n",
    "                elif j == i:\n",
    "                    dp[i][j] = dp[i-1][j - 1] + dp[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j] + dp[i][j], dp[i-1][j - 1] + dp[i][j])\n",
    "        return min(dp[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        dp = [float('inf')]*n\n",
    "        dp[0] = triangle[0][0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i-1]+triangle[i][i]\n",
    "            for j in range(i-1, 0, -1):\n",
    "                dp[j] = min(dp[j], dp[j-1])+triangle[i][j]\n",
    "            dp[0] = dp[0]+triangle[i][0]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        row = len(triangle)\n",
    "        dp = [0] * row\n",
    "        for i in range(len(triangle[-1])):\n",
    "            dp[i] = triangle[-1][i]\n",
    "        #print(dp)\n",
    "        for i in range(row - 2, -1, -1):\n",
    "            for j in range(i + 1):\n",
    "                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]\n",
    "        return dp[0]  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        # fi = min(f[i+1,j],f[i+1,j+1])+a[i]\n",
    "        f = [0] * (len(triangle) + 1)\n",
    "        for row in triangle[::-1]:\n",
    "            for i in range(len(row)):\n",
    "                f[i] = row[i]+min(f[i],f[i+1])\n",
    "        return f[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        # total = triangle[0][0]\n",
    "        # triangle[0] = (triangle[0], triangle[0])\n",
    "        for i in range(1, len(triangle)):\n",
    "            for j in range(len(triangle[i])):\n",
    "                if j == 0:\n",
    "                    weight = triangle[i-1][j]\n",
    "                elif j == len(triangle[i])-1:\n",
    "                    weight = triangle[i-1][j-1]\n",
    "                else:\n",
    "                    weight = min(triangle[i-1][j-1], triangle[i-1][j])\n",
    "\n",
    "                triangle[i][j] = triangle[i][j] + weight\n",
    "\n",
    "                # triangle[i][j] = min(triangle[i][j] + weight, triangle[i][j-1] if j-1 >= 0 else float('inf'))\n",
    "                \n",
    "                # triangle[j] = (triangle[j], min(triangle[i-1][j-1], triangle[i-1][j]))\n",
    "        \n",
    "        return min(triangle[len(triangle)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        f[0][0] = triangle[0][0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            f[i][0] = f[i - 1][0] + triangle[i][0]\n",
    "            for j in range(1, i):\n",
    "                f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]\n",
    "            f[i][i] = f[i - 1][i - 1] + triangle[i][i]\n",
    "        return min(f[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        dp = [[float('inf')]*len(triangle[i]) for i in range(len(triangle))]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(len(triangle)):\n",
    "            for j in range(len(triangle[i])):\n",
    "                if i==0 and j==0:continue\n",
    "                if j==0:\n",
    "                    dp[i][j] = dp[i-1][j]+triangle[i][j]\n",
    "                    continue\n",
    "                if j==len(triangle[i])-1:\n",
    "                    dp[i][j] = dp[i-1][j-1]+triangle[i][j]\n",
    "                    continue\n",
    "                dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]\n",
    "        return min(dp[len(triangle)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        m = len(triangle)\n",
    "        dp =  [[0 for i in range(m)] for j in range(m)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        for i in range(1,m):\n",
    "            for j in range(i+1):\n",
    "                if j==0:\n",
    "                    dp[i][j] = dp[i-1][j] + triangle[i][j]\n",
    "                elif j==i:\n",
    "                    dp[i][j] = dp[i-1][j-1] + triangle[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]\n",
    "       \n",
    "        return min(dp[m-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        n = len(triangle)\n",
    "        m = len(triangle[-1])\n",
    "        dp = [[0] * m for i in range(n)]\n",
    "        dp[0][0] = triangle[0][0]\n",
    "        print(dp)\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1):\n",
    "                print(i,j)\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + triangle[i][j]\n",
    "                elif j == i:\n",
    "                    dp[i][j] = dp[i-1][j-1] + triangle[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]\n",
    "        return min(dp[-1])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
